int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}
// 排序解法
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
int longestConsecutive(int* nums, int numsSize) {
    if (numsSize < 2) return numsSize;

    qsort(nums, numsSize, sizeof(int), compare);

    int ans = 1;
    int count = 1;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] == nums[i - 1]) continue;

        if (nums[i] - nums[i - 1] == 1) {
            count++;
        } else {
            ans = fmax(ans, count);
            count = 1;
        }
    }

    return fmax(ans, count);
}

// 哈希查找解法
// 时间复杂度：O(n)
// 空间复杂度：O(n)
// 使用 uthash.h ：https://blog.csdn.net/Dusong_/article/details/128757067

#include <stdio.h>
#include <stdbool.h>
#include "uthash.h"

// 定义一个结构体表示哈希表，在哈希表中只存储 key
struct hash_node {
    int key;
    UT_hash_handle hh;  // 用于添加到哈希表中
};

int longestConsecutive(int* nums, int numsSize) {
    if (numsSize < 2) return numsSize;

    // 创建一个哈希表
    struct hash_node* hashTable = NULL;
    struct hash_node* tempNode;

    // 将所有数字插入哈希表，去掉重复元素
    for (int i = 0; i < numsSize; i++) {
        HASH_FIND_INT(hashTable, &nums[i], tempNode);
        if (tempNode == NULL) {
            struct hash_node* node;
            node = (struct hash_node*) malloc(sizeof(*node));
            node->key = nums[i];
            HASH_ADD_INT(hashTable, key, node);
        }
    }

    int ans = 1;
    struct hash_node* currentNode, *tmp;
    // 遍历所有数字
    HASH_ITER(hh, hashTable, currentNode, tmp) {
        if (currentNode != NULL) {
            int prevNum = currentNode->key - 1;
            HASH_FIND_INT(hashTable, &prevNum, tempNode);
            // 如果当前数字的前一个数字已经在哈希表中，说明当前数字已经被计算过了，跳过本次循环
            if (tempNode != NULL) continue;

            int currNum = currentNode->key + 1;
            int count = 1;
            // 计算以当前数字为起点的最长连续序列
            HASH_FIND_INT(hashTable, &currNum, tempNode);
            while (tempNode != NULL) {
                currNum++;
                count++;
                HASH_FIND_INT(hashTable, &currNum, tempNode);
            }

            ans = ans > count ? ans : count;
        }
    }

    // 遍历完所有数字后，释放哈希表结点所占用的内存
    HASH_ITER(hh, hashTable, currentNode, tmp) {
        HASH_DEL(hashTable, currentNode);
        free(currentNode);
    }

    return ans;
}
